#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rof(i,a,b) for(int i=a;i>=b;--i)
#define rep(i,a) for(int i=1;i<=a;++i)
#define print(x) printf("%lld\n",(int)x)
#define prn(x) printf("%lld ",(int)x)
using namespace std;
const int N=2e6+5,Mod=998244353;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=(ch=='-'?-f:f);ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int T,a,b;
inline int calc(int x,int y){return x*y/__gcd(x,y);}
signed main(){
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	T=read();
	while(T--){
		a=read(),b=read();
		if(b%a==0){printf("%lld\n",b);continue;}
		if(__gcd(a,b)>1){printf("%lld\n",min(a+b,calc(a,b)));continue;}
		int s=a,t=b;
		For(i,2,sqrt(a)){
			if(a%i==0){
				s=i;
				break;
			}
		}
		For(i,2,sqrt(b)){
			if(b%i==0){
				t=i;
				break;
			}
		}
		int ans=calc(a,b);//a-b
		ans=min(ans,calc(a,s)+calc(s,2)+calc(2,t)+calc(t,b));//a-s-2-t-b
		ans=min(ans,calc(a,s)+calc(s,t)+calc(t,b));//a-s-t-b
		ans=min(ans,calc(a,s)+calc(s,2)+calc(2,b));//a-s-2-b
		ans=min(ans,calc(a,2)+calc(2,t)+calc(t,b));//a-2-t-b
		ans=min(ans,calc(a,s)+calc(s,b));//a-s-b
		ans=min(ans,calc(a,2)+calc(2,b));//a-2-b
		ans=min(ans,calc(a,t)+calc(t,b));//a-t-b
		
		printf("%lld\n",ans);
	}
	return 0;
}
//
